package projects;

import java.io.BufferedWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;
import java.util.TreeSet;

public class DTTools {

	public static double bestGain(double[][] features, double[] labels, ArrayList<Double> attributes) {
		
		double[] gains = new double[attributes.size()];
		for (int i = 0; i < gains.length; i++) {
			gains[i] = gain(features, labels, attributes.get(i));
		}
		
		int bestGainIndex = 0;
		double bestGain = 0.0;
		for (int i = 0; i < gains.length; i++) {
			if (gains[i] > bestGain) {
				bestGain = gains[i];
				bestGainIndex = i;
			}
		}
		return attributes.get(bestGainIndex);
	}
	
	public static double gain(double[][] features, double[] labels, double attribute) {
		
		double gain = entropy(labels);
		
		ArrayList<Double> values = getValues(features, attribute);
		for (double value : values) {
			double[] subsetLabels = subsetLabels(features, labels, attribute, value);
			double subsetEntropy = entropy(subsetLabels);
			gain -= (double)subsetLabels.length / (double)labels.length * subsetEntropy;
		}
		return gain;
	}
	
	public static double entropy(double[] labels) {
		
		double entropy = 0.0;
		double valueCount = getNumClasses(labels);
		
		for (int labelValue = 0; labelValue < valueCount; labelValue++) {
			double probability = probability(labelValue, labels);
			entropy -= probability * logBase2(probability);
		}
		return entropy;
	}
	
	public static double probability(double value, double[] labels) {	
		
		double numRows = labels.length;
		double numRowsOfThisClass = 0.0;
		
		for (int i = 0; i < numRows; i++) 
			if (labels[i] == value)
				numRowsOfThisClass += 1;
		
		double probability = numRowsOfThisClass / numRows;
		return probability;
	}
	
	public static double logBase2(double number) {
		if (number == 0) return 0;
		return Math.log(number) / Math.log(2);
	}
	
		
	public static boolean allValuesAreSame(double[] array) {
		double firstLabel = array[0];
		for (int i = 0; i < array.length; i++)
			if (array[i] != firstLabel)
				return false;
		return true;
	}
	
	public static double[][] subsetFeatures(double[][] features, double attribute, double attributeValue) {
		ArrayList<double[]> rowsToKeep = new ArrayList<double[]>();
		for (int i = 0; i < features.length; i++)
			if (features[i][(int)attribute] == attributeValue)
				rowsToKeep.add(features[i]);
		return rowsToKeep.toArray(new double[0][0]);
	}

	public static double[] subsetLabels(double[][] features, double[] labels, 
			double attribute, double attributeValue) {
		
		ArrayList<Double> subsetLabels = new ArrayList<Double>();
		for (int row = 0; row < labels.length; row++)
			if (features[row][(int)attribute] == attributeValue) 
				subsetLabels.add(labels[row]);
				
		return arrayListToArray(subsetLabels);
	}
	
	public static ArrayList<Double> getValues(double[][] array, double attribute) {
		ArrayList<Double> values = new ArrayList<Double>();
		for (int i = 0; i < array.length; i++) {
			if (!values.contains(array[i][(int)attribute]))
				values.add(array[i][(int)attribute]);
		}
		return values;
	}
	
	public static int getNumClasses(double[] array) {
		TreeSet<Double> alreadySeen = new TreeSet<Double>();
		for (int i = 0; i < array.length; i++) {
			alreadySeen.add(array[i]);
		}
		return alreadySeen.size();
	}
	
	public static double[] arrayListToArray(ArrayList<Double> arrayList) {
		double[] array = new double[arrayList.size()];
		for (int i = 0; i < arrayList.size(); i++)
			array[i] = arrayList.get(i);	
		return array;		
	}
	
	public static double[] matrixToArray(Matrix matrix) {
		double[] array = new double[matrix.rows()];
		for (int i = 0; i < matrix.rows(); i++)
			array[i] = matrix.get(i, 0);
		return array;
	}
	
	public static double[][] matrixTo2DArray(Matrix matrix) {
		double[][] array = new double[matrix.rows()][matrix.cols()];
		for (int i = 0; i < matrix.rows(); i++)
			for (int j = 0; j < matrix.cols(); j++)
				array[i][j] = matrix.get(i, j);
		return array;
	}
	
	public static void print2DArray(String name, double[][] array) {
		System.out.println(name + ":");
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				System.out.print(array[i][j] + "\t");
			}
			System.out.println();
		}
	}

	public static void printArray(String name, double[] array) {
		System.out.println(name + ":");
		for (int i = 0; i < array.length; i++)
			System.out.println(array[i]);
	}
	
	public static double mostCommonValueIn(double[] array) {
		
		int[] arrayCounts = new int[1000];
		for (int i = 0; i < array.length; i++) {
			int value = (int)array[i];
			arrayCounts[value]++;
		}
		
		int mostCommonIndex = 0;
		int mostCommonValue = 0;
		for (int i = 0; i < arrayCounts.length; i++) {
			if (arrayCounts[i] > mostCommonValue) {
				mostCommonValue = arrayCounts[i];
				mostCommonIndex = i;
			}
		}
		return mostCommonIndex;
	}

	public static void printTree(DTNode node, BufferedWriter writer) {
		try {
			writer.write("\np:::: ");
			node.printNode(writer);
			if (node.hasChildren()) {
				ArrayList<DTNode> children = node.getChildren();
				ArrayList<DTNode> grandchildren = new ArrayList<DTNode>();
				writer.write("\nc:::: ");
				for(DTNode child : children) {
					child.printNode(writer);
					grandchildren.addAll(child.getChildren());
				}
				writer.write("\ngc:::: ");
				for (DTNode gc : grandchildren)
					gc.printNode(writer);
			}	
		}catch (IOException e) { e.printStackTrace(); }
	}
	
	public static Matrix saveValidationFeatures(Matrix features) {
		Random rand = new Random(1);
		features.shuffle(rand);
		Matrix valFeatures = new Matrix(features, 0, 0, features.rows() / 5, features.cols());
		return valFeatures;
	}
	
	public static Matrix nonValidationFeatures(Matrix features) {
		Random rand = new Random(1);
		features.shuffle(rand);
		Matrix nonValFeatures = new Matrix(features, features.rows() / 5, 0, 
				features.rows() - features.rows() / 5, features.cols());
		return nonValFeatures;
	}	
	
	public static double[][] throwOutUnknowns(double[][] features) {
		ArrayList<Double[]> reducedFeatures = new ArrayList<Double[]>();
		for (int i = 0; i < features.length; i++) {
			boolean hasUnknown = false;
			for (int j = 0; j < features[i].length; j++) {
				if (features[i][j] == 1.7976931348623157E308)
					hasUnknown = true;
			}
			if (!hasUnknown) {
				Double[] featuresRow = new Double[features[i].length];
				for (int k = 0; k < featuresRow.length; k++)
					featuresRow[k] = (Double)features[i][k];
				reducedFeatures.add(featuresRow);
			}
		}
		
		double[][] reducedFeaturesArr = new double[reducedFeatures.size()][];
		for (int i = 0; i < reducedFeatures.size(); i++) {
			reducedFeaturesArr[i] = new double[reducedFeatures.get(i).length];
			for (int j = 0; j < reducedFeatures.get(i).length; j++) {
				reducedFeaturesArr[i][j] = (double)reducedFeatures.get(i)[j];
			}
		}
		return reducedFeaturesArr;
	}

	public static double[] throwOutUnknowns(double[] labels, double[][] features) {
		ArrayList<Double> reducedLabels = new ArrayList<Double>();
		for (int i = 0; i < features.length; i++) {
			boolean hasUnknown = false;
			for (int j = 0; j < features[i].length; j++) {
				if (features[i][j] == 1.7976931348623157E308)
					hasUnknown = true;
			}
			if (!hasUnknown) {
				reducedLabels.add(labels[i]);
			}
		}
		
		return arrayListToArray(reducedLabels);
	}
	

	public static void test(double[][] features, double[] labels, 
			ArrayList<Double> attributes) {
		
		System.out.println("Testing DTTools");
		
		printArray("labels", labels);
		System.out.println("most common: " + mostCommonValueIn(labels));
		
		double bestGainAttribute = bestGain(features, labels, attributes);
		System.out.println("Best Gain Attribute: " + bestGainAttribute);
		
		double entropy = entropy(labels);		
		System.out.println("entropy: " + entropy + "\n");
		
		entropy = entropy(subsetLabels(features, labels, 0, 0));
		System.out.println("entropy-0-0: " + entropy);

		entropy = entropy(subsetLabels(features, labels, 0, 1));
		System.out.println("entropy-0-1: " + entropy);

		entropy = entropy(subsetLabels(features, labels, 0, 2));
		System.out.println("entropy-0-2: " + entropy + "\n");

		entropy = entropy(subsetLabels(features, labels, 1, 0));
		System.out.println("entropy-1-0: " + entropy);

		entropy = entropy(subsetLabels(features, labels, 1, 1));
		System.out.println("entropy-1-1: " + entropy);

		entropy = entropy(subsetLabels(features, labels, 1, 2));
		System.out.println("entropy-1-2: " + entropy + "\n");

		entropy = entropy(subsetLabels(features, labels, 2, 0));
		System.out.println("entropy-2-0: " + entropy);

		entropy = entropy(subsetLabels(features, labels, 2, 1));
		System.out.println("entropy-2-1: " + entropy + "\n");

		entropy = entropy(subsetLabels(features, labels, 3, 0));
		System.out.println("entropy-3-0: " + entropy);

		entropy = entropy(subsetLabels(features, labels, 3, 1));
		System.out.println("entropy-3-1: " + entropy + "\n");
		
		double[][] subsetFeatures = subsetFeatures(features, 0, 0);
		print2DArray("features", features);
		print2DArray("subsetFeatures", subsetFeatures);
		
		double[] subsetLabels = subsetLabels(features, labels, 0, 0);
		printArray("labels", labels);
		printArray("subsetLabels", subsetLabels);
		
		double gain0 = gain(features, labels, 0);
		System.out.println("gain: " + gain0);
		
		double gain1 = gain(features, labels, 1);
		System.out.println("gain: " + gain1);
		
		double gain2 = gain(features, labels, 2);
		System.out.println("gain: " + gain2);
		
		double gain3 = gain(features, labels, 3);
		System.out.println("gain: " + gain3);
	}
}
